package com.lovi.horseChess;

import lombok.Data;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;

public class Test01 {
    public static void main(String[] args) {
        int step = 1;
//        1.创建棋盘 chessBoard,是二维数组
        //创建棋盘8*8
        int[][] chessBoard = new int[8][8];
//        2,将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走
//        哪些位置,并放入到一个集合中(ArrayList),最多有8个,
        //初始化棋盘位置为(4,4),最中间，测试看看返回的list
        ArrayList<Post> posts = checkStep(4, 4, step, chessBoard);
//        posts.forEach(System.out::println);
//        每走一步,就 step +1
//        3,遍历ArrayList中存放的所有位置,看看那个可以走,如果可以走
//        通,就继续,走不通,就回溯
        if (recursionStep(4, 4, step, chessBoard, posts)) {
            System.out.println("找到啦！！这是打印！");
            printChessBoard(chessBoard);
        }else {
            System.out.println("没找到！！也打印当前");
            printChessBoard(chessBoard);
        }
//        4,判断马儿是否完成了任务,使用step和应该走的步数比较,如果
//        没有达到数量,则表示没有完成任务,将整个棋盘设置为0
//        注意：马儿走的策略不同，则得到的结果也不一样，效率也不一样.
    }

    /**
     * 2,将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走
     * 哪些位置,并放入到一个集合中(ArrayList),最多有8个
     * 参数：位置设置，棋盘本身
     * 返回：马儿还能走哪些位置的ArrayList,还有当前的step值
     * 注意奥：棋盘的边界情况判定
     * 为了方便，我们的step值实际上就是马儿走的第几步，在棋盘上会显示数字
     */
    public static ArrayList<Post> checkStep(int x, int y, int step, int[][] chessBoard) {
        //1. 将当前位置设置为已经访问,不为0就是已经访问的(不需要在这设置，你只是个工具，谢谢）
//        chessBoard[x][y] = step;
        //2.根据当前位置,计算马儿还能走哪些位置
        ArrayList<Post> list = new ArrayList<>();
        int[] newXArray = {x - 1, x + 1, x - 2, x + 2, x - 2, x + 2, x - 1, x + 1};
        int[] newYArray = {y - 2, y - 2, y - 1, y - 1, y + 1, y + 1, y + 2, y + 2};
        for (int i = 0; i < 8; i++) {
            int newX = newXArray[i], newY = newYArray[i];
            //边界条件
            if (0 <= newX && newX <= 7 && 0 <= newY && newY <= 7) {
                //并且，这个坐标在棋盘中是0【说明没走过】
                if (chessBoard[newX][newY] == 0 || chessBoard[newX][newY] >= step) {
                    Post post = new Post();
                    post.setX(newX);
                    post.setY(newY);
                    list.add(post);
                }
            }
        }
        return list;

    }


    /**
     * 2.遍历ArrayList中存放的所有位置,看看那个可以走,如果可以走
     * 通,就继续,走不通,就回溯
     * 参数，棋盘本身，ArrayList,走动的 x,y
     * 返回值？暂时不需要【直接修改棋盘即可】
     * 关于step，传过来的step是当前的步数，也就是x,y对应的步数
     * 混乱：step应该在哪设置？
     * 在哪判断step是不是为64
     * <p>
     * <p>
     * 思考：目标是list里面的节点，如果当前不可以走，那也可以尝试走当前的下一个！而不是直接就回溯到上一步
     */
    public static boolean recursionStep(int x, int y, int step, int[][] chessBoard, ArrayList<Post> list) {
        //这里的是step是指的是，x,y对应的步数
        if (step == 64) {
            //说明找到啦！！
            chessBoard[x][y] = step;
            return true;
        }
        for (Post post : list) {
            ArrayList<Post> newList = checkStep(post.getX(), post.getY(), step + 1, chessBoard);
//            if (chessBoard[post.getX()][post.getY()] != 0) {
//                //说明这个点已经被其他位置来的list的点走过了，直接跳过这个点
//                continue;
//            }
            //关于是否可以走，是看，下一个节点的list是否为空，如果为空，则表示不能走，回溯即可
            if (newList.isEmpty()) {
                // 集合中的当前点走不通
                // 把不能走的坐标设置回0【好像没走过的点本来就是0...】
//                chessBoard[post.getX()][post.getY()] = 0;
            } else {
                //确定当前点是可以走的,并且当前点没被走过才设置值
                if (chessBoard[x][y] == 0 || chessBoard[x][y] >= step) {
                    chessBoard[x][y] = step;
                }else {
                    //当前已经是更早的步数了，说明之前走过，那么就不应该走这个点
                    continue;
                }
                //list的当前点是走得通的，那我们就继续走，只要是通的就会继续走
                //递归
                //这里到底要不要return，这里return我们才可以有回溯链路！
                //走得通就继续走，一旦有true，就会返回上一个是true，然后就可以找到true
                //一旦有false？当一个集合全部走完了，只要有一个false，它还是....
                if (chessBoard[post.getX()][post.getY()] == 0 || chessBoard[post.getX()][post.getY()] >= step) {
                    if (recursionStep(post.getX(), post.getY(), step + 1, chessBoard, newList)) {
                        //回溯过程中为假则不中断，继续走下一个点，如果为真则保持真的链路
//                    chessBoard[post.getX()][post.getY()] = step + 1;
                        return true;
                    }
                }
            }
        }

        // 那就对这个点返回false
        //并且设置这个点为0，变成可以走！（会绕圈子出不去！）
//        chessBoard[x][y] = 0;
        //这个点全部能走的集合都走完了，还是没找到，因此回溯到上一个点
        return false;
    }

    /**
     * 打印当前的棋盘情况
     */
    public static void printChessBoard(int[][] chessBoard) {
        for (int i = 0; i < chessBoard.length; i++) {
            for (int j = 0; j < chessBoard[i].length; j++) {
                System.out.print(chessBoard[i][j] + "\t");
            }
            System.out.println();
        }
    }

}

//记录坐标
@Data
class Post {
    private int x;
    private int y;

}
